package com.algorithm.cjm.csnote

/**
 * 分治法
 *
 * Created by jieming.chen on 2021/2/16
 */

//fun divide_and_conquer(n) {
//    if (n <= n0) {  // n为问题规模， n0 为可解子问题的规模
//        // 解子问题
//        return (子问题的解);
//    }
//    for (i in 1..k) { // 分解为较小的k个子问题 P1, P2,...,Pk
//        yi = divide_and_conquer(|Pi|) // 递归解决 Pi， |Pi| 为 Pi的规模
//    }
//    T = Merge(y1, y2, ..., yk) // 合并子问题
//    return (T);
//}

/**
 *
Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output : [0, 2]
 * 给表达式加括号
 */
fun diffWaysToCompute(input: String): List<Int> {
    val results = mutableListOf<Int>()
    for (i in 1 until input.length) {
        // 循环当遇到字符 +,-,* 时，分解子问题
        val char = input[i]
        if (char == '+' || char == '-' || char == '*') {
            // 按照运算符的两边分解为 左右子问题
            var left = diffWaysToCompute(input.substring(0, i))
            var right = diffWaysToCompute(input.substring(i+1, input.length))
            // 按照左右子问题的 求解
            for (j in left.indices)
                for (k in right.indices)
                    if (char == '+') {
                        results.add(left[j] + right[k])
                    } else if (char == '-') {
                        results.add(left[j] - right[k])
                    } else if (char == '*') {
                        results.add(left[j] * right[k])
                    }
        }
    }
    // 字符串只有一个字符，结果就为那个字符
    if (results.size == 0) {
        results.add(Integer.valueOf(input.substring(0, 1)))
    }
    return results
}

/**
 *
 * 1. 分解
 * 2. 解决
 * 3. 合并
 */
fun generateTrees(n: Int): List<TreeNode?> {
    return generateTrees(1, n)
}

fun generateTrees(min: Int, max: Int): List<TreeNode?> {
    val mutableList = mutableListOf<TreeNode?>()
    if (min > max) {
        // 2. 解决子问题
        mutableList.add(null)
        return mutableList
    }
    for (i in min.. max) {
        // 1. 分解子问题
        val leftTree = generateTrees(min, i - 1)
        val rightTree = generateTrees(i + 1, max)

        // 3. 合并子问题的解为原问题的解
        for (j in leftTree.indices) {
            for (k in rightTree.indices) {
                // 2. 解决子问题
                val rootNode = TreeNode(i)
                rootNode.leftChild = leftTree[j]
                rootNode.rightChild = rightTree[k]
                mutableList.add(rootNode)
            }
        }
    }
    return mutableList
}

fun main(args: Array<String>) {
    val computes = diffWaysToCompute("2*3-4*5")
    println(computes.toIntArray().contentToString())
}


